package com.example.demo.Calss18_dongtaiguihua;

/**
 * @program: java_base
 * @description: 背包问题
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/04 09:07
 */
public class Code01_KnapsackDemo {

    /**
     * 集合内元素 均为非负值
     * [1,3,5,7,4,2,1,5,7] 货物重量
     * [3,6,7,8,9,9,3,5,7] 货物价值
     * 描述：向背包内放置货物，要求在背包容量允许的情况下，价值最大！
     */
    /**
     * @param w     货物重量集合
     * @param v     货物价值集合
     * @param index 当前货物和价值索引
     * @param rest  背包剩余容量
     * @return
     */
    public static  int process(int[] w, int[] v, int index, int rest) {
        // 边界条件
        // base case
        if (rest < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
//        经典错误！！！！！判断背包容量和索引越界，顺序不可变！！！还是对语义没有十分了解！！！
//        if (rest < 0) {
//            return -1;
//        }

        int p1 = process(w, v, index + 1, rest);

        int p2 = 0;
        int next = process(w, v, index + 1, rest - w[index]);
        p2 = next != -1 ? v[index] + next : 0;
        // 选择index 不选择index

        // 如果不选择 index 的话，
        return Math.max(p1, p2);
    }
    // 所有的货，重量和价值，都在w和v数组里
    // 为了方便，其中没有负数
    // bag背包容量，不能超过这个载重
    // 返回：不超重的情况下，能够得到的最大价值
    public static int maxValue(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        // 尝试函数！
        return process(w, v, 0, bag);
    }


    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
        int[] values = { 5, 6, 3, 19, 12, 4, 2 };
        int bag = 15;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(dp(weights, values, bag));
    }


    public static int dp(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1) {
                    p2 = v[index] + next;
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }
}
